package org.example;

public class Test2 {
    //leetcode 134 加油站 https://leetcode.cn/problems/gas-station/description/
    /**
     * 一半样例过不去
     * @param gas
     * @param cost
     * @return
     */
    public int canCompleteCircuit1(int[] gas, int[] cost) {
        int n = gas.length;
        int[] tmp = new int[2 * n];
        for (int i = 0; i < n; i++) {
            tmp[i] = tmp[i + n] = gas[i] - cost[i];
        }
        int i = 0, remain = 0, step = 0;
        for (; i < 2 * n && step < n; i++) {
            remain += tmp[i];
            if (remain >= 0) step++;
            else {
                remain = 0;
                step = 0;
            }
        }
        return step == 0 ? -1 : i;
    }

    /**
     * 超时，剩三个样例
     * @param gas
     * @param cost
     * @return
     */
    public int canCompleteCircuit2(int[] gas, int[] cost) {
        int n = gas.length;
        int[] tmp = new int[n];
        for (int i = 0; i < n; i++) {
            tmp[i] = gas[i] - cost[i];
        }
        int index = 0, remain = 0, step = 0, count = 0;
        for (;index < n && step < n && count < n; index = (index + 1) % n) {
            remain += tmp[index];
            if (remain >= 0) {
                step++;
            }else {
                count++;
                step = 0;
                remain = 0;
            }
        }
        return step == n ? index : -1;
    }

    /**
     * totalTank用来记录gas[i]-cost[i]的和，如果totalTank<0，则无法环绕一周
     * currTank则用来记录从i位置开始向i+1个加油站走，油箱中剩的汽油，startingStation则用来记录从那个加油站开始走的
     * 如果currTank<0，则表示从i之前的所有位置开始都无法完成环绕一圈，所以startingStation = i + 1
     * @param gas
     * @param cost
     * @return
     */
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalTank = 0;
        int currTank = 0;
        int startingStation = 0;

        for (int i = 0; i < gas.length; i++) {
            int netGain = gas[i] - cost[i];
            totalTank += netGain;
            currTank += netGain;

            // If currTank is negative, we can't reach the next station from this starting point
            if (currTank < 0) {
                // Start from the next station
                //为什么这里的startingStation直接等于i+1了呢，startingStation ~ i之间的起始位置就不考虑了吗
                //是的，因为要想到下一个加油站就必须保证gas[i]-cost[i]为正数,
                //gas[startingStation]-cost[startingStation] + x + nums[i]<0,那么x+nums[i]一定<0
                //x为从startingStation+1位置开始到i-1位置剩余的汽油,以此类推以startingStation+2，startingStation+3
                //为起始位置的情况都不能成功到达i位置
                startingStation = i + 1;
                // Reset current tank
                currTank = 0;
            }
        }

        // If totalTank is negative, it means we can't complete the circuit
        return totalTank >= 0 ? startingStation : -1;
    }

    public static void main(String[] args) {
        int[] gas = {4};
        int[] cost = {5};
        Test2 test2 = new Test2();
        test2.canCompleteCircuit(gas,cost);
        System.out.println(555);
    }
}
